package datastruct.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author Gorchun
 * @create 2021/2/26 11:13
 */
public class Utils {

    public int[] treeNodes;
    public int length = 0;
    public TreeNode root;

    public Utils(int[] init){
        root = null;
        treeNodes = init.clone();
    }
    public Utils(){
        root = null;
        treeNodes = new int[]{-1};
    }
    //递归建树
    public TreeNode createTreeNode(TreeNode root){
        int val = treeNodes[length++];
        if(val != -1){
            root = new TreeNode(val);
            root.left = createTreeNode(root.left);
            root.right = createTreeNode(root.right);
        }
        return root;
    }

    //先序遍历（递归）
    public void preShow(TreeNode root){
        if(root != null){
            System.out.print(root.val + " ");
            preShow(root.left);
            preShow(root.right);
        }
    }

    //中序遍历（递归）
    public void normShow(TreeNode root){
        if(root != null){
            normShow(root.left);
            System.out.print(root.val + " ");
            normShow(root.right);
        }
    }

    //后序遍历（递归）
    public void postShow(TreeNode root){
        if(root != null) {
            postShow(root.left);
            postShow(root.right);
            System.out.print(root.val + " ");
        }
    }

    //层次遍历（非递归）
    public void layerShow(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) queue.offer(tmp.left);
                if(tmp.right != null) queue.offer(tmp.right);
                System.out.print(tmp.val + " ");
            }
        }
        System.out.println();
    }

    //先序遍历（非递归）
    public void pre2Show(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode tmp = stack.pop();
            if(stack.size() == 0) break;
            System.out.print(tmp.val + " ");
            root = tmp.right;
        }
    }

    //带层数先序递归遍历
    public void preShowAddLayer(TreeNode root, int layer){
        if(root != null){
            System.out.println("root val:" + root.val + " layer:" + layer);
            preShowAddLayer(root.left, layer+1);
            preShowAddLayer(root.right, layer+1);
        }
    }

    //指定查找某节点层数
    public int findNodeLayer(TreeNode root, int val, int layer){
        int res = -1;
        if(root != null){
            if(root.val == val){
                return layer;
            }
            res = findNodeLayer(root.left, val, layer+1);
            if(res != -1) return res;
            res = findNodeLayer(root.right, val, layer+1);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root = new Utils(new int[]{1,2,4,-1,-1,5,-1,-1,3,6,-1,-1,7,-1,-1}).createTreeNode(root);
        new Utils().preShow(root);
    }

    // Encodes a datastruct to a single string.
    public String serialize(TreeNode root) {
        //扩展先序遍历：把节点的null也遍历到, val1+","+val2+","+...
        StringBuilder sb = new StringBuilder();
        extendPreOrderSerialize(root,sb);
        return sb.toString();
    }

    public void extendPreOrderSerialize(TreeNode root, StringBuilder sb){
        if(root==null) sb.append("null,");
        else {
            sb.append(root.val);
            sb.append(",");
            extendPreOrderSerialize(root.left,sb);
            extendPreOrderSerialize(root.right,sb);
        }
    }

    // Decodes your encoded data to datastruct.
    public static TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(vals));
        return extendPreOrderDeserialize(queue);
    }


    public static TreeNode extendPreOrderDeserialize(Queue<String> queue){
        String curNode = queue.poll();
        if("null".equals(curNode)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(curNode));
        root.left = extendPreOrderDeserialize(queue);
        root.right = extendPreOrderDeserialize(queue);
        return root;
    }

}
